package study.datastructure.queue.leetcode;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-10-26 19:55
 * <p>
 * 2024/10/26,
 * <p>
 * 2024/10/26,
 */

/**
 2024/10/26,
 */

import study.datastructure.queue.impl.LinkedListQueue;
import study.datastructure.queue.Queue;

import java.util.LinkedList;
import java.util.List;

/**
 * 给你二叉树的根节点 root
 * ，返回其节点值的 锯齿形层序遍历
 * （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）
 */
public class Client103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //返回结果
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }

        //存放下一层的节点的集合
        Queue<TreeNode> queue = new LinkedListQueue<>();
        queue.offer(root);

        int count1 = 1;//当前层的节点数

        boolean odd=true;

        while (!queue.isEmpty()) {

            int kids = 0; //下一层的节点数
            LinkedList<Integer> level = new LinkedList<>(); //存放当前层的节点值
            for (int i = 0; i < count1; i++) {
                TreeNode n = queue.poll();
                if(odd){
                    level.offerLast(n.val);
                }else {
                    level.offerFirst(n.val);
                }
                if (n.left != null) {
                    kids++;
                    queue.offer(n.left);
                }
                if (n.right != null) {
                    kids++;
                    queue.offer(n.right);
                            
                }

            }

            odd = ! odd; //判别奇偶层
            count1 = kids;
            result.add(level);

        }

        return result;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        // 创建一个二叉树
        Client103 client = new Client103();
        TreeNode root = client.new TreeNode(3);
        root.left = client.new TreeNode(9);
        root.right = client.new TreeNode(20);
        root.right.left = client.new TreeNode(15);
        root.right.right = client.new TreeNode(7);

        // 调用 zigzagLevelOrder 方法
        List<List<Integer>> result = client.zigzagLevelOrder(root);

        // 打印结果
        for (List<Integer> level : result) {
            System.out.println(level);
        }
    }
}
